
<!DOCTYPE html>

<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta charset="utf-8" />
    <title>collections &#8212; Spatial Maths package 0.7.0
 documentation</title>
    <link rel="stylesheet" href="../_static/alabaster.css" type="text/css" />
    <link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
    <link rel="stylesheet" type="text/css" href="../_static/graphviz.css" />
    <script id="documentation_options" data-url_root="../" src="../_static/documentation_options.js"></script>
    <script src="../_static/jquery.js"></script>
    <script src="../_static/underscore.js"></script>
    <script src="../_static/doctools.js"></script>
    <script src="../_static/language_data.js"></script>
    <script async="async" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
    <link rel="index" title="Index" href="../genindex.html" />
    <link rel="search" title="Search" href="../search.html" />
   
  <link rel="stylesheet" href="../_static/custom.css" type="text/css" />
  
  
  <meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />

  </head><body>
  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          

          <div class="body" role="main">
            
  <h1>Source code for collections</h1><div class="highlight"><pre>
<span></span><span class="sd">&#39;&#39;&#39;This module implements specialized container datatypes providing</span>
<span class="sd">alternatives to Python&#39;s general purpose built-in containers, dict,</span>
<span class="sd">list, set, and tuple.</span>

<span class="sd">* namedtuple   factory function for creating tuple subclasses with named fields</span>
<span class="sd">* deque        list-like container with fast appends and pops on either end</span>
<span class="sd">* ChainMap     dict-like class for creating a single view of multiple mappings</span>
<span class="sd">* Counter      dict subclass for counting hashable objects</span>
<span class="sd">* OrderedDict  dict subclass that remembers the order entries were added</span>
<span class="sd">* defaultdict  dict subclass that calls a factory function to supply missing values</span>
<span class="sd">* UserDict     wrapper around dictionary objects for easier dict subclassing</span>
<span class="sd">* UserList     wrapper around list objects for easier list subclassing</span>
<span class="sd">* UserString   wrapper around string objects for easier string subclassing</span>

<span class="sd">&#39;&#39;&#39;</span>

<span class="n">__all__</span> <span class="o">=</span> <span class="p">[</span><span class="s1">&#39;deque&#39;</span><span class="p">,</span> <span class="s1">&#39;defaultdict&#39;</span><span class="p">,</span> <span class="s1">&#39;namedtuple&#39;</span><span class="p">,</span> <span class="s1">&#39;UserDict&#39;</span><span class="p">,</span> <span class="s1">&#39;UserList&#39;</span><span class="p">,</span>
            <span class="s1">&#39;UserString&#39;</span><span class="p">,</span> <span class="s1">&#39;Counter&#39;</span><span class="p">,</span> <span class="s1">&#39;OrderedDict&#39;</span><span class="p">,</span> <span class="s1">&#39;ChainMap&#39;</span><span class="p">]</span>

<span class="kn">import</span> <span class="nn">_collections_abc</span>
<span class="kn">from</span> <span class="nn">operator</span> <span class="kn">import</span> <span class="n">itemgetter</span> <span class="k">as</span> <span class="n">_itemgetter</span><span class="p">,</span> <span class="n">eq</span> <span class="k">as</span> <span class="n">_eq</span>
<span class="kn">from</span> <span class="nn">keyword</span> <span class="kn">import</span> <span class="n">iskeyword</span> <span class="k">as</span> <span class="n">_iskeyword</span>
<span class="kn">import</span> <span class="nn">sys</span> <span class="k">as</span> <span class="nn">_sys</span>
<span class="kn">import</span> <span class="nn">heapq</span> <span class="k">as</span> <span class="nn">_heapq</span>
<span class="kn">from</span> <span class="nn">_weakref</span> <span class="kn">import</span> <span class="n">proxy</span> <span class="k">as</span> <span class="n">_proxy</span>
<span class="kn">from</span> <span class="nn">itertools</span> <span class="kn">import</span> <span class="n">repeat</span> <span class="k">as</span> <span class="n">_repeat</span><span class="p">,</span> <span class="n">chain</span> <span class="k">as</span> <span class="n">_chain</span><span class="p">,</span> <span class="n">starmap</span> <span class="k">as</span> <span class="n">_starmap</span>
<span class="kn">from</span> <span class="nn">reprlib</span> <span class="kn">import</span> <span class="n">recursive_repr</span> <span class="k">as</span> <span class="n">_recursive_repr</span>

<span class="k">try</span><span class="p">:</span>
    <span class="kn">from</span> <span class="nn">_collections</span> <span class="kn">import</span> <span class="n">deque</span>
<span class="k">except</span> <span class="ne">ImportError</span><span class="p">:</span>
    <span class="k">pass</span>
<span class="k">else</span><span class="p">:</span>
    <span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableSequence</span><span class="o">.</span><span class="n">register</span><span class="p">(</span><span class="n">deque</span><span class="p">)</span>

<span class="k">try</span><span class="p">:</span>
    <span class="kn">from</span> <span class="nn">_collections</span> <span class="kn">import</span> <span class="n">defaultdict</span>
<span class="k">except</span> <span class="ne">ImportError</span><span class="p">:</span>
    <span class="k">pass</span>


<span class="k">def</span> <span class="fm">__getattr__</span><span class="p">(</span><span class="n">name</span><span class="p">):</span>
    <span class="c1"># For backwards compatibility, continue to make the collections ABCs</span>
    <span class="c1"># through Python 3.6 available through the collections module.</span>
    <span class="c1"># Note, no new collections ABCs were added in Python 3.7</span>
    <span class="k">if</span> <span class="n">name</span> <span class="ow">in</span> <span class="n">_collections_abc</span><span class="o">.</span><span class="n">__all__</span><span class="p">:</span>
        <span class="n">obj</span> <span class="o">=</span> <span class="nb">getattr</span><span class="p">(</span><span class="n">_collections_abc</span><span class="p">,</span> <span class="n">name</span><span class="p">)</span>
        <span class="kn">import</span> <span class="nn">warnings</span>
        <span class="n">warnings</span><span class="o">.</span><span class="n">warn</span><span class="p">(</span><span class="s2">&quot;Using or importing the ABCs from &#39;collections&#39; instead &quot;</span>
                      <span class="s2">&quot;of from &#39;collections.abc&#39; is deprecated since Python 3.3,&quot;</span>
                      <span class="s2">&quot;and in 3.9 it will stop working&quot;</span><span class="p">,</span>
                      <span class="ne">DeprecationWarning</span><span class="p">,</span> <span class="n">stacklevel</span><span class="o">=</span><span class="mi">2</span><span class="p">)</span>
        <span class="nb">globals</span><span class="p">()[</span><span class="n">name</span><span class="p">]</span> <span class="o">=</span> <span class="n">obj</span>
        <span class="k">return</span> <span class="n">obj</span>
    <span class="k">raise</span> <span class="ne">AttributeError</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;module </span><span class="si">{</span><span class="vm">__name__</span><span class="si">!r}</span><span class="s1"> has no attribute </span><span class="si">{</span><span class="n">name</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>

<span class="c1">################################################################################</span>
<span class="c1">### OrderedDict</span>
<span class="c1">################################################################################</span>

<span class="k">class</span> <span class="nc">_OrderedDictKeysView</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">KeysView</span><span class="p">):</span>

    <span class="k">def</span> <span class="fm">__reversed__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">yield from</span> <span class="nb">reversed</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_mapping</span><span class="p">)</span>

<span class="k">class</span> <span class="nc">_OrderedDictItemsView</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">ItemsView</span><span class="p">):</span>

    <span class="k">def</span> <span class="fm">__reversed__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="nb">reversed</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_mapping</span><span class="p">):</span>
            <span class="k">yield</span> <span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_mapping</span><span class="p">[</span><span class="n">key</span><span class="p">])</span>

<span class="k">class</span> <span class="nc">_OrderedDictValuesView</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">ValuesView</span><span class="p">):</span>

    <span class="k">def</span> <span class="fm">__reversed__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="nb">reversed</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_mapping</span><span class="p">):</span>
            <span class="k">yield</span> <span class="bp">self</span><span class="o">.</span><span class="n">_mapping</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>

<span class="k">class</span> <span class="nc">_Link</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
    <span class="vm">__slots__</span> <span class="o">=</span> <span class="s1">&#39;prev&#39;</span><span class="p">,</span> <span class="s1">&#39;next&#39;</span><span class="p">,</span> <span class="s1">&#39;key&#39;</span><span class="p">,</span> <span class="s1">&#39;__weakref__&#39;</span>

<span class="k">class</span> <span class="nc">OrderedDict</span><span class="p">(</span><span class="nb">dict</span><span class="p">):</span>
    <span class="s1">&#39;Dictionary that remembers insertion order&#39;</span>
    <span class="c1"># An inherited dict maps keys to values.</span>
    <span class="c1"># The inherited dict provides __getitem__, __len__, __contains__, and get.</span>
    <span class="c1"># The remaining methods are order-aware.</span>
    <span class="c1"># Big-O running times for all methods are the same as regular dictionaries.</span>

    <span class="c1"># The internal self.__map dict maps keys to links in a doubly linked list.</span>
    <span class="c1"># The circular doubly linked list starts and ends with a sentinel element.</span>
    <span class="c1"># The sentinel element never gets deleted (this simplifies the algorithm).</span>
    <span class="c1"># The sentinel is in self.__hardroot with a weakref proxy in self.__root.</span>
    <span class="c1"># The prev links are weakref proxies (to prevent circular references).</span>
    <span class="c1"># Individual links are kept alive by the hard reference in self.__map.</span>
    <span class="c1"># Those hard references disappear when a key is deleted from an OrderedDict.</span>

    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Initialize an ordered dictionary.  The signature is the same as</span>
<span class="sd">        regular dictionaries.  Keyword argument order is preserved.</span>
<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="n">args</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s2">&quot;descriptor &#39;__init__&#39; of &#39;OrderedDict&#39; object &quot;</span>
                            <span class="s2">&quot;needs an argument&quot;</span><span class="p">)</span>
        <span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span> <span class="o">=</span> <span class="n">args</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">)</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s1">&#39;expected at most 1 arguments, got </span><span class="si">%d</span><span class="s1">&#39;</span> <span class="o">%</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">))</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
        <span class="k">except</span> <span class="ne">AttributeError</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">__hardroot</span> <span class="o">=</span> <span class="n">_Link</span><span class="p">()</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">__root</span> <span class="o">=</span> <span class="n">root</span> <span class="o">=</span> <span class="n">_proxy</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">__hardroot</span><span class="p">)</span>
            <span class="n">root</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">root</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">__map</span> <span class="o">=</span> <span class="p">{}</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">__update</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">)</span>

    <span class="k">def</span> <span class="fm">__setitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">,</span>
                    <span class="n">dict_setitem</span><span class="o">=</span><span class="nb">dict</span><span class="o">.</span><span class="fm">__setitem__</span><span class="p">,</span> <span class="n">proxy</span><span class="o">=</span><span class="n">_proxy</span><span class="p">,</span> <span class="n">Link</span><span class="o">=</span><span class="n">_Link</span><span class="p">):</span>
        <span class="s1">&#39;od.__setitem__(i, y) &lt;==&gt; od[i]=y&#39;</span>
        <span class="c1"># Setting a new item creates a new link at the end of the linked list,</span>
        <span class="c1"># and the inherited dictionary is updated with the new key/value pair.</span>
        <span class="k">if</span> <span class="n">key</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">link</span> <span class="o">=</span> <span class="n">Link</span><span class="p">()</span>
            <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
            <span class="n">last</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">prev</span>
            <span class="n">link</span><span class="o">.</span><span class="n">prev</span><span class="p">,</span> <span class="n">link</span><span class="o">.</span><span class="n">next</span><span class="p">,</span> <span class="n">link</span><span class="o">.</span><span class="n">key</span> <span class="o">=</span> <span class="n">last</span><span class="p">,</span> <span class="n">root</span><span class="p">,</span> <span class="n">key</span>
            <span class="n">last</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link</span>
            <span class="n">root</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">proxy</span><span class="p">(</span><span class="n">link</span><span class="p">)</span>
        <span class="n">dict_setitem</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">)</span>

    <span class="k">def</span> <span class="fm">__delitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">dict_delitem</span><span class="o">=</span><span class="nb">dict</span><span class="o">.</span><span class="fm">__delitem__</span><span class="p">):</span>
        <span class="s1">&#39;od.__delitem__(y) &lt;==&gt; del od[y]&#39;</span>
        <span class="c1"># Deleting an existing item uses self.__map to find the link which gets</span>
        <span class="c1"># removed by updating the links in the predecessor and successor nodes.</span>
        <span class="n">dict_delitem</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">)</span>
        <span class="n">link</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
        <span class="n">link_prev</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">prev</span>
        <span class="n">link_next</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">next</span>
        <span class="n">link_prev</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link_next</span>
        <span class="n">link_next</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">link_prev</span>
        <span class="n">link</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="kc">None</span>
        <span class="n">link</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="kc">None</span>

    <span class="k">def</span> <span class="fm">__iter__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;od.__iter__() &lt;==&gt; iter(od)&#39;</span>
        <span class="c1"># Traverse the linked list in order.</span>
        <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
        <span class="n">curr</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">next</span>
        <span class="k">while</span> <span class="n">curr</span> <span class="ow">is</span> <span class="ow">not</span> <span class="n">root</span><span class="p">:</span>
            <span class="k">yield</span> <span class="n">curr</span><span class="o">.</span><span class="n">key</span>
            <span class="n">curr</span> <span class="o">=</span> <span class="n">curr</span><span class="o">.</span><span class="n">next</span>

    <span class="k">def</span> <span class="fm">__reversed__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;od.__reversed__() &lt;==&gt; reversed(od)&#39;</span>
        <span class="c1"># Traverse the linked list in reverse order.</span>
        <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
        <span class="n">curr</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">prev</span>
        <span class="k">while</span> <span class="n">curr</span> <span class="ow">is</span> <span class="ow">not</span> <span class="n">root</span><span class="p">:</span>
            <span class="k">yield</span> <span class="n">curr</span><span class="o">.</span><span class="n">key</span>
            <span class="n">curr</span> <span class="o">=</span> <span class="n">curr</span><span class="o">.</span><span class="n">prev</span>

    <span class="k">def</span> <span class="nf">clear</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;od.clear() -&gt; None.  Remove all items from od.&#39;</span>
        <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
        <span class="n">root</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">root</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="o">.</span><span class="n">clear</span><span class="p">()</span>
        <span class="nb">dict</span><span class="o">.</span><span class="n">clear</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">popitem</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">last</span><span class="o">=</span><span class="kc">True</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Remove and return a (key, value) pair from the dictionary.</span>

<span class="sd">        Pairs are returned in LIFO order if last is true or FIFO order if false.</span>
<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="s1">&#39;dictionary is empty&#39;</span><span class="p">)</span>
        <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
        <span class="k">if</span> <span class="n">last</span><span class="p">:</span>
            <span class="n">link</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">prev</span>
            <span class="n">link_prev</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">prev</span>
            <span class="n">link_prev</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">root</span>
            <span class="n">root</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">link_prev</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">link</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">next</span>
            <span class="n">link_next</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">next</span>
            <span class="n">root</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link_next</span>
            <span class="n">link_next</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">root</span>
        <span class="n">key</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">key</span>
        <span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
        <span class="n">value</span> <span class="o">=</span> <span class="nb">dict</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span>

    <span class="k">def</span> <span class="nf">move_to_end</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">last</span><span class="o">=</span><span class="kc">True</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Move an existing element to the end (or beginning if last is false).</span>

<span class="sd">        Raise KeyError if the element does not exist.</span>
<span class="sd">        &#39;&#39;&#39;</span>
        <span class="n">link</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
        <span class="n">link_prev</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">prev</span>
        <span class="n">link_next</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">next</span>
        <span class="n">soft_link</span> <span class="o">=</span> <span class="n">link_next</span><span class="o">.</span><span class="n">prev</span>
        <span class="n">link_prev</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link_next</span>
        <span class="n">link_next</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">link_prev</span>
        <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
        <span class="k">if</span> <span class="n">last</span><span class="p">:</span>
            <span class="n">last</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">prev</span>
            <span class="n">link</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">last</span>
            <span class="n">link</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">root</span>
            <span class="n">root</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">soft_link</span>
            <span class="n">last</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">first</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">next</span>
            <span class="n">link</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">root</span>
            <span class="n">link</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">first</span>
            <span class="n">first</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">soft_link</span>
            <span class="n">root</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link</span>

    <span class="k">def</span> <span class="nf">__sizeof__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="n">sizeof</span> <span class="o">=</span> <span class="n">_sys</span><span class="o">.</span><span class="n">getsizeof</span>
        <span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span>                       <span class="c1"># number of links including root</span>
        <span class="n">size</span> <span class="o">=</span> <span class="n">sizeof</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">)</span>            <span class="c1"># instance dictionary</span>
        <span class="n">size</span> <span class="o">+=</span> <span class="n">sizeof</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="p">)</span> <span class="o">*</span> <span class="mi">2</span>          <span class="c1"># internal dict and inherited dict</span>
        <span class="n">size</span> <span class="o">+=</span> <span class="n">sizeof</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">__hardroot</span><span class="p">)</span> <span class="o">*</span> <span class="n">n</span>     <span class="c1"># link objects</span>
        <span class="n">size</span> <span class="o">+=</span> <span class="n">sizeof</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">__root</span><span class="p">)</span> <span class="o">*</span> <span class="n">n</span>         <span class="c1"># proxy objects</span>
        <span class="k">return</span> <span class="n">size</span>

    <span class="n">update</span> <span class="o">=</span> <span class="n">__update</span> <span class="o">=</span> <span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableMapping</span><span class="o">.</span><span class="n">update</span>

    <span class="k">def</span> <span class="nf">keys</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s2">&quot;D.keys() -&gt; a set-like object providing a view on D&#39;s keys&quot;</span>
        <span class="k">return</span> <span class="n">_OrderedDictKeysView</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">items</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s2">&quot;D.items() -&gt; a set-like object providing a view on D&#39;s items&quot;</span>
        <span class="k">return</span> <span class="n">_OrderedDictItemsView</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">values</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s2">&quot;D.values() -&gt; an object providing a view on D&#39;s values&quot;</span>
        <span class="k">return</span> <span class="n">_OrderedDictValuesView</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

    <span class="fm">__ne__</span> <span class="o">=</span> <span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableMapping</span><span class="o">.</span><span class="fm">__ne__</span>

    <span class="n">__marker</span> <span class="o">=</span> <span class="nb">object</span><span class="p">()</span>

    <span class="k">def</span> <span class="nf">pop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="o">=</span><span class="n">__marker</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;od.pop(k[,d]) -&gt; v, remove specified key and return the corresponding</span>
<span class="sd">        value.  If key is not found, d is returned if given, otherwise KeyError</span>
<span class="sd">        is raised.</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="n">result</span> <span class="o">=</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
            <span class="k">del</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
            <span class="k">return</span> <span class="n">result</span>
        <span class="k">if</span> <span class="n">default</span> <span class="ow">is</span> <span class="bp">self</span><span class="o">.</span><span class="n">__marker</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">default</span>

    <span class="k">def</span> <span class="nf">setdefault</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Insert key with a value of default if key is not in the dictionary.</span>

<span class="sd">        Return the value for key if key is in the dictionary, else default.</span>
<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
        <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">default</span>
        <span class="k">return</span> <span class="n">default</span>

    <span class="nd">@_recursive_repr</span><span class="p">()</span>
    <span class="k">def</span> <span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;od.__repr__() &lt;==&gt; repr(od)&#39;</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="p">:</span>
            <span class="k">return</span> <span class="s1">&#39;</span><span class="si">%s</span><span class="s1">()&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span><span class="p">,)</span>
        <span class="k">return</span> <span class="s1">&#39;</span><span class="si">%s</span><span class="s1">(</span><span class="si">%r</span><span class="s1">)&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span><span class="p">,</span> <span class="nb">list</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">()))</span>

    <span class="k">def</span> <span class="nf">__reduce__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;Return state information for pickling&#39;</span>
        <span class="n">inst_dict</span> <span class="o">=</span> <span class="nb">vars</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span>
        <span class="k">for</span> <span class="n">k</span> <span class="ow">in</span> <span class="nb">vars</span><span class="p">(</span><span class="n">OrderedDict</span><span class="p">()):</span>
            <span class="n">inst_dict</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="kc">None</span><span class="p">)</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">,</span> <span class="p">(),</span> <span class="n">inst_dict</span> <span class="ow">or</span> <span class="kc">None</span><span class="p">,</span> <span class="kc">None</span><span class="p">,</span> <span class="nb">iter</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">())</span>

    <span class="k">def</span> <span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;od.copy() -&gt; a shallow copy of od&#39;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

    <span class="nd">@classmethod</span>
    <span class="k">def</span> <span class="nf">fromkeys</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">,</span> <span class="n">value</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Create a new ordered dictionary with keys from iterable and values set to value.</span>
<span class="sd">        &#39;&#39;&#39;</span>
        <span class="bp">self</span> <span class="o">=</span> <span class="bp">cls</span><span class="p">()</span>
        <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="n">iterable</span><span class="p">:</span>
            <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">value</span>
        <span class="k">return</span> <span class="bp">self</span>

    <span class="k">def</span> <span class="fm">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;od.__eq__(y) &lt;==&gt; od==y.  Comparison to another OD is order-sensitive</span>
<span class="sd">        while comparison to a regular mapping is order-insensitive.</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">OrderedDict</span><span class="p">):</span>
            <span class="k">return</span> <span class="nb">dict</span><span class="o">.</span><span class="fm">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">)</span> <span class="ow">and</span> <span class="nb">all</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="n">_eq</span><span class="p">,</span> <span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">))</span>
        <span class="k">return</span> <span class="nb">dict</span><span class="o">.</span><span class="fm">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">)</span>


<span class="k">try</span><span class="p">:</span>
    <span class="kn">from</span> <span class="nn">_collections</span> <span class="kn">import</span> <span class="n">OrderedDict</span>
<span class="k">except</span> <span class="ne">ImportError</span><span class="p">:</span>
    <span class="c1"># Leave the pure Python version in place.</span>
    <span class="k">pass</span>


<span class="c1">################################################################################</span>
<span class="c1">### namedtuple</span>
<span class="c1">################################################################################</span>

<span class="n">_nt_itemgetters</span> <span class="o">=</span> <span class="p">{}</span>

<span class="k">def</span> <span class="nf">namedtuple</span><span class="p">(</span><span class="n">typename</span><span class="p">,</span> <span class="n">field_names</span><span class="p">,</span> <span class="o">*</span><span class="p">,</span> <span class="n">rename</span><span class="o">=</span><span class="kc">False</span><span class="p">,</span> <span class="n">defaults</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">module</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;Returns a new subclass of tuple with named fields.</span>

<span class="sd">    &gt;&gt;&gt; Point = namedtuple(&#39;Point&#39;, [&#39;x&#39;, &#39;y&#39;])</span>
<span class="sd">    &gt;&gt;&gt; Point.__doc__                   # docstring for the new class</span>
<span class="sd">    &#39;Point(x, y)&#39;</span>
<span class="sd">    &gt;&gt;&gt; p = Point(11, y=22)             # instantiate with positional args or keywords</span>
<span class="sd">    &gt;&gt;&gt; p[0] + p[1]                     # indexable like a plain tuple</span>
<span class="sd">    33</span>
<span class="sd">    &gt;&gt;&gt; x, y = p                        # unpack like a regular tuple</span>
<span class="sd">    &gt;&gt;&gt; x, y</span>
<span class="sd">    (11, 22)</span>
<span class="sd">    &gt;&gt;&gt; p.x + p.y                       # fields also accessible by name</span>
<span class="sd">    33</span>
<span class="sd">    &gt;&gt;&gt; d = p._asdict()                 # convert to a dictionary</span>
<span class="sd">    &gt;&gt;&gt; d[&#39;x&#39;]</span>
<span class="sd">    11</span>
<span class="sd">    &gt;&gt;&gt; Point(**d)                      # convert from a dictionary</span>
<span class="sd">    Point(x=11, y=22)</span>
<span class="sd">    &gt;&gt;&gt; p._replace(x=100)               # _replace() is like str.replace() but targets named fields</span>
<span class="sd">    Point(x=100, y=22)</span>

<span class="sd">    &quot;&quot;&quot;</span>

    <span class="c1"># Validate the field names.  At the user&#39;s option, either generate an error</span>
    <span class="c1"># message or automatically replace the field name with a valid name.</span>
    <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">field_names</span><span class="p">,</span> <span class="nb">str</span><span class="p">):</span>
        <span class="n">field_names</span> <span class="o">=</span> <span class="n">field_names</span><span class="o">.</span><span class="n">replace</span><span class="p">(</span><span class="s1">&#39;,&#39;</span><span class="p">,</span> <span class="s1">&#39; &#39;</span><span class="p">)</span><span class="o">.</span><span class="n">split</span><span class="p">()</span>
    <span class="n">field_names</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="nb">str</span><span class="p">,</span> <span class="n">field_names</span><span class="p">))</span>
    <span class="n">typename</span> <span class="o">=</span> <span class="n">_sys</span><span class="o">.</span><span class="n">intern</span><span class="p">(</span><span class="nb">str</span><span class="p">(</span><span class="n">typename</span><span class="p">))</span>

    <span class="k">if</span> <span class="n">rename</span><span class="p">:</span>
        <span class="n">seen</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span>
        <span class="k">for</span> <span class="n">index</span><span class="p">,</span> <span class="n">name</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">field_names</span><span class="p">):</span>
            <span class="k">if</span> <span class="p">(</span><span class="ow">not</span> <span class="n">name</span><span class="o">.</span><span class="n">isidentifier</span><span class="p">()</span>
                <span class="ow">or</span> <span class="n">_iskeyword</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>
                <span class="ow">or</span> <span class="n">name</span><span class="o">.</span><span class="n">startswith</span><span class="p">(</span><span class="s1">&#39;_&#39;</span><span class="p">)</span>
                <span class="ow">or</span> <span class="n">name</span> <span class="ow">in</span> <span class="n">seen</span><span class="p">):</span>
                <span class="n">field_names</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="sa">f</span><span class="s1">&#39;_</span><span class="si">{</span><span class="n">index</span><span class="si">}</span><span class="s1">&#39;</span>
            <span class="n">seen</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>

    <span class="k">for</span> <span class="n">name</span> <span class="ow">in</span> <span class="p">[</span><span class="n">typename</span><span class="p">]</span> <span class="o">+</span> <span class="n">field_names</span><span class="p">:</span>
        <span class="k">if</span> <span class="nb">type</span><span class="p">(</span><span class="n">name</span><span class="p">)</span> <span class="ow">is</span> <span class="ow">not</span> <span class="nb">str</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s1">&#39;Type names and field names must be strings&#39;</span><span class="p">)</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="n">name</span><span class="o">.</span><span class="n">isidentifier</span><span class="p">():</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s1">&#39;Type names and field names must be valid &#39;</span>
                             <span class="sa">f</span><span class="s1">&#39;identifiers: </span><span class="si">{</span><span class="n">name</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>
        <span class="k">if</span> <span class="n">_iskeyword</span><span class="p">(</span><span class="n">name</span><span class="p">):</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s1">&#39;Type names and field names cannot be a &#39;</span>
                             <span class="sa">f</span><span class="s1">&#39;keyword: </span><span class="si">{</span><span class="n">name</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>

    <span class="n">seen</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span>
    <span class="k">for</span> <span class="n">name</span> <span class="ow">in</span> <span class="n">field_names</span><span class="p">:</span>
        <span class="k">if</span> <span class="n">name</span><span class="o">.</span><span class="n">startswith</span><span class="p">(</span><span class="s1">&#39;_&#39;</span><span class="p">)</span> <span class="ow">and</span> <span class="ow">not</span> <span class="n">rename</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s1">&#39;Field names cannot start with an underscore: &#39;</span>
                             <span class="sa">f</span><span class="s1">&#39;</span><span class="si">{</span><span class="n">name</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>
        <span class="k">if</span> <span class="n">name</span> <span class="ow">in</span> <span class="n">seen</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Encountered duplicate field name: </span><span class="si">{</span><span class="n">name</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>
        <span class="n">seen</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>

    <span class="n">field_defaults</span> <span class="o">=</span> <span class="p">{}</span>
    <span class="k">if</span> <span class="n">defaults</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
        <span class="n">defaults</span> <span class="o">=</span> <span class="nb">tuple</span><span class="p">(</span><span class="n">defaults</span><span class="p">)</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">defaults</span><span class="p">)</span> <span class="o">&gt;</span> <span class="nb">len</span><span class="p">(</span><span class="n">field_names</span><span class="p">):</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s1">&#39;Got more default values than field names&#39;</span><span class="p">)</span>
        <span class="n">field_defaults</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">(</span><span class="nb">reversed</span><span class="p">(</span><span class="nb">list</span><span class="p">(</span><span class="nb">zip</span><span class="p">(</span><span class="nb">reversed</span><span class="p">(</span><span class="n">field_names</span><span class="p">),</span>
                                                <span class="nb">reversed</span><span class="p">(</span><span class="n">defaults</span><span class="p">)))))</span>

    <span class="c1"># Variables used in the methods and docstrings</span>
    <span class="n">field_names</span> <span class="o">=</span> <span class="nb">tuple</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="n">_sys</span><span class="o">.</span><span class="n">intern</span><span class="p">,</span> <span class="n">field_names</span><span class="p">))</span>
    <span class="n">num_fields</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">field_names</span><span class="p">)</span>
    <span class="n">arg_list</span> <span class="o">=</span> <span class="nb">repr</span><span class="p">(</span><span class="n">field_names</span><span class="p">)</span><span class="o">.</span><span class="n">replace</span><span class="p">(</span><span class="s2">&quot;&#39;&quot;</span><span class="p">,</span> <span class="s2">&quot;&quot;</span><span class="p">)[</span><span class="mi">1</span><span class="p">:</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span>
    <span class="n">repr_fmt</span> <span class="o">=</span> <span class="s1">&#39;(&#39;</span> <span class="o">+</span> <span class="s1">&#39;, &#39;</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;</span><span class="si">{</span><span class="n">name</span><span class="si">}</span><span class="s1">=%r&#39;</span> <span class="k">for</span> <span class="n">name</span> <span class="ow">in</span> <span class="n">field_names</span><span class="p">)</span> <span class="o">+</span> <span class="s1">&#39;)&#39;</span>
    <span class="n">tuple_new</span> <span class="o">=</span> <span class="nb">tuple</span><span class="o">.</span><span class="fm">__new__</span>
    <span class="n">_len</span> <span class="o">=</span> <span class="nb">len</span>

    <span class="c1"># Create all the named tuple methods to be added to the class namespace</span>

    <span class="n">s</span> <span class="o">=</span> <span class="sa">f</span><span class="s1">&#39;def __new__(_cls, </span><span class="si">{</span><span class="n">arg_list</span><span class="si">}</span><span class="s1">): return _tuple_new(_cls, (</span><span class="si">{</span><span class="n">arg_list</span><span class="si">}</span><span class="s1">))&#39;</span>
    <span class="n">namespace</span> <span class="o">=</span> <span class="p">{</span><span class="s1">&#39;_tuple_new&#39;</span><span class="p">:</span> <span class="n">tuple_new</span><span class="p">,</span> <span class="s1">&#39;__name__&#39;</span><span class="p">:</span> <span class="sa">f</span><span class="s1">&#39;namedtuple_</span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1">&#39;</span><span class="p">}</span>
    <span class="c1"># Note: exec() has the side-effect of interning the field names</span>
    <span class="n">exec</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">namespace</span><span class="p">)</span>
    <span class="fm">__new__</span> <span class="o">=</span> <span class="n">namespace</span><span class="p">[</span><span class="s1">&#39;__new__&#39;</span><span class="p">]</span>
    <span class="fm">__new__</span><span class="o">.</span><span class="vm">__doc__</span> <span class="o">=</span> <span class="sa">f</span><span class="s1">&#39;Create new instance of </span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1">(</span><span class="si">{</span><span class="n">arg_list</span><span class="si">}</span><span class="s1">)&#39;</span>
    <span class="k">if</span> <span class="n">defaults</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
        <span class="fm">__new__</span><span class="o">.</span><span class="vm">__defaults__</span> <span class="o">=</span> <span class="n">defaults</span>

    <span class="nd">@classmethod</span>
    <span class="k">def</span> <span class="nf">_make</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">):</span>
        <span class="n">result</span> <span class="o">=</span> <span class="n">tuple_new</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">)</span>
        <span class="k">if</span> <span class="n">_len</span><span class="p">(</span><span class="n">result</span><span class="p">)</span> <span class="o">!=</span> <span class="n">num_fields</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Expected </span><span class="si">{</span><span class="n">num_fields</span><span class="si">}</span><span class="s1"> arguments, got </span><span class="si">{</span><span class="nb">len</span><span class="p">(</span><span class="n">result</span><span class="p">)</span><span class="si">}</span><span class="s1">&#39;</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="n">_make</span><span class="o">.</span><span class="vm">__func__</span><span class="o">.</span><span class="vm">__doc__</span> <span class="o">=</span> <span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Make a new </span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1"> object from a sequence &#39;</span>
                              <span class="s1">&#39;or iterable&#39;</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">_replace</span><span class="p">(</span><span class="n">_self</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
        <span class="n">result</span> <span class="o">=</span> <span class="n">_self</span><span class="o">.</span><span class="n">_make</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="n">kwds</span><span class="o">.</span><span class="n">pop</span><span class="p">,</span> <span class="n">field_names</span><span class="p">,</span> <span class="n">_self</span><span class="p">))</span>
        <span class="k">if</span> <span class="n">kwds</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Got unexpected field names: </span><span class="si">{</span><span class="nb">list</span><span class="p">(</span><span class="n">kwds</span><span class="p">)</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="n">_replace</span><span class="o">.</span><span class="vm">__doc__</span> <span class="o">=</span> <span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Return a new </span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1"> object replacing specified &#39;</span>
                        <span class="s1">&#39;fields with new values&#39;</span><span class="p">)</span>

    <span class="k">def</span> <span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;Return a nicely formatted representation string&#39;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span> <span class="o">+</span> <span class="n">repr_fmt</span> <span class="o">%</span> <span class="bp">self</span>

    <span class="k">def</span> <span class="nf">_asdict</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;Return a new OrderedDict which maps field names to their values.&#39;</span>
        <span class="k">return</span> <span class="n">OrderedDict</span><span class="p">(</span><span class="nb">zip</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_fields</span><span class="p">,</span> <span class="bp">self</span><span class="p">))</span>

    <span class="k">def</span> <span class="nf">__getnewargs__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;Return self as a plain tuple.  Used by copy and pickle.&#39;</span>
        <span class="k">return</span> <span class="nb">tuple</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

    <span class="c1"># Modify function metadata to help with introspection and debugging</span>

    <span class="k">for</span> <span class="n">method</span> <span class="ow">in</span> <span class="p">(</span><span class="fm">__new__</span><span class="p">,</span> <span class="n">_make</span><span class="o">.</span><span class="vm">__func__</span><span class="p">,</span> <span class="n">_replace</span><span class="p">,</span>
                   <span class="fm">__repr__</span><span class="p">,</span> <span class="n">_asdict</span><span class="p">,</span> <span class="n">__getnewargs__</span><span class="p">):</span>
        <span class="n">method</span><span class="o">.</span><span class="vm">__qualname__</span> <span class="o">=</span> <span class="sa">f</span><span class="s1">&#39;</span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1">.</span><span class="si">{</span><span class="n">method</span><span class="o">.</span><span class="vm">__name__</span><span class="si">}</span><span class="s1">&#39;</span>

    <span class="c1"># Build-up the class namespace dictionary</span>
    <span class="c1"># and use type() to build the result class</span>
    <span class="n">class_namespace</span> <span class="o">=</span> <span class="p">{</span>
        <span class="s1">&#39;__doc__&#39;</span><span class="p">:</span> <span class="sa">f</span><span class="s1">&#39;</span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1">(</span><span class="si">{</span><span class="n">arg_list</span><span class="si">}</span><span class="s1">)&#39;</span><span class="p">,</span>
        <span class="s1">&#39;__slots__&#39;</span><span class="p">:</span> <span class="p">(),</span>
        <span class="s1">&#39;_fields&#39;</span><span class="p">:</span> <span class="n">field_names</span><span class="p">,</span>
        <span class="s1">&#39;_field_defaults&#39;</span><span class="p">:</span> <span class="n">field_defaults</span><span class="p">,</span>
        <span class="c1"># alternate spelling for backward compatibility</span>
        <span class="s1">&#39;_fields_defaults&#39;</span><span class="p">:</span> <span class="n">field_defaults</span><span class="p">,</span>
        <span class="s1">&#39;__new__&#39;</span><span class="p">:</span> <span class="fm">__new__</span><span class="p">,</span>
        <span class="s1">&#39;_make&#39;</span><span class="p">:</span> <span class="n">_make</span><span class="p">,</span>
        <span class="s1">&#39;_replace&#39;</span><span class="p">:</span> <span class="n">_replace</span><span class="p">,</span>
        <span class="s1">&#39;__repr__&#39;</span><span class="p">:</span> <span class="fm">__repr__</span><span class="p">,</span>
        <span class="s1">&#39;_asdict&#39;</span><span class="p">:</span> <span class="n">_asdict</span><span class="p">,</span>
        <span class="s1">&#39;__getnewargs__&#39;</span><span class="p">:</span> <span class="n">__getnewargs__</span><span class="p">,</span>
    <span class="p">}</span>
    <span class="n">cache</span> <span class="o">=</span> <span class="n">_nt_itemgetters</span>
    <span class="k">for</span> <span class="n">index</span><span class="p">,</span> <span class="n">name</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">field_names</span><span class="p">):</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="n">itemgetter_object</span><span class="p">,</span> <span class="n">doc</span> <span class="o">=</span> <span class="n">cache</span><span class="p">[</span><span class="n">index</span><span class="p">]</span>
        <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
            <span class="n">itemgetter_object</span> <span class="o">=</span> <span class="n">_itemgetter</span><span class="p">(</span><span class="n">index</span><span class="p">)</span>
            <span class="n">doc</span> <span class="o">=</span> <span class="sa">f</span><span class="s1">&#39;Alias for field number </span><span class="si">{</span><span class="n">index</span><span class="si">}</span><span class="s1">&#39;</span>
            <span class="n">cache</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="n">itemgetter_object</span><span class="p">,</span> <span class="n">doc</span>
        <span class="n">class_namespace</span><span class="p">[</span><span class="n">name</span><span class="p">]</span> <span class="o">=</span> <span class="nb">property</span><span class="p">(</span><span class="n">itemgetter_object</span><span class="p">,</span> <span class="n">doc</span><span class="o">=</span><span class="n">doc</span><span class="p">)</span>

    <span class="n">result</span> <span class="o">=</span> <span class="nb">type</span><span class="p">(</span><span class="n">typename</span><span class="p">,</span> <span class="p">(</span><span class="nb">tuple</span><span class="p">,),</span> <span class="n">class_namespace</span><span class="p">)</span>

    <span class="c1"># For pickling to work, the __module__ variable needs to be set to the frame</span>
    <span class="c1"># where the named tuple is created.  Bypass this step in environments where</span>
    <span class="c1"># sys._getframe is not defined (Jython for example) or sys._getframe is not</span>
    <span class="c1"># defined for arguments greater than 0 (IronPython), or where the user has</span>
    <span class="c1"># specified a particular module.</span>
    <span class="k">if</span> <span class="n">module</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="n">module</span> <span class="o">=</span> <span class="n">_sys</span><span class="o">.</span><span class="n">_getframe</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span><span class="o">.</span><span class="n">f_globals</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s1">&#39;__name__&#39;</span><span class="p">,</span> <span class="s1">&#39;__main__&#39;</span><span class="p">)</span>
        <span class="k">except</span> <span class="p">(</span><span class="ne">AttributeError</span><span class="p">,</span> <span class="ne">ValueError</span><span class="p">):</span>
            <span class="k">pass</span>
    <span class="k">if</span> <span class="n">module</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
        <span class="n">result</span><span class="o">.</span><span class="vm">__module__</span> <span class="o">=</span> <span class="n">module</span>

    <span class="k">return</span> <span class="n">result</span>


<span class="c1">########################################################################</span>
<span class="c1">###  Counter</span>
<span class="c1">########################################################################</span>

<span class="k">def</span> <span class="nf">_count_elements</span><span class="p">(</span><span class="n">mapping</span><span class="p">,</span> <span class="n">iterable</span><span class="p">):</span>
    <span class="s1">&#39;Tally elements from the iterable.&#39;</span>
    <span class="n">mapping_get</span> <span class="o">=</span> <span class="n">mapping</span><span class="o">.</span><span class="n">get</span>
    <span class="k">for</span> <span class="n">elem</span> <span class="ow">in</span> <span class="n">iterable</span><span class="p">:</span>
        <span class="n">mapping</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">mapping_get</span><span class="p">(</span><span class="n">elem</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span>

<span class="k">try</span><span class="p">:</span>                                    <span class="c1"># Load C helper function if available</span>
    <span class="kn">from</span> <span class="nn">_collections</span> <span class="kn">import</span> <span class="n">_count_elements</span>
<span class="k">except</span> <span class="ne">ImportError</span><span class="p">:</span>
    <span class="k">pass</span>

<span class="k">class</span> <span class="nc">Counter</span><span class="p">(</span><span class="nb">dict</span><span class="p">):</span>
    <span class="sd">&#39;&#39;&#39;Dict subclass for counting hashable items.  Sometimes called a bag</span>
<span class="sd">    or multiset.  Elements are stored as dictionary keys and their counts</span>
<span class="sd">    are stored as dictionary values.</span>

<span class="sd">    &gt;&gt;&gt; c = Counter(&#39;abcdeabcdabcaba&#39;)  # count elements from a string</span>

<span class="sd">    &gt;&gt;&gt; c.most_common(3)                # three most common elements</span>
<span class="sd">    [(&#39;a&#39;, 5), (&#39;b&#39;, 4), (&#39;c&#39;, 3)]</span>
<span class="sd">    &gt;&gt;&gt; sorted(c)                       # list all unique elements</span>
<span class="sd">    [&#39;a&#39;, &#39;b&#39;, &#39;c&#39;, &#39;d&#39;, &#39;e&#39;]</span>
<span class="sd">    &gt;&gt;&gt; &#39;&#39;.join(sorted(c.elements()))   # list elements with repetitions</span>
<span class="sd">    &#39;aaaaabbbbcccdde&#39;</span>
<span class="sd">    &gt;&gt;&gt; sum(c.values())                 # total of all counts</span>
<span class="sd">    15</span>

<span class="sd">    &gt;&gt;&gt; c[&#39;a&#39;]                          # count of letter &#39;a&#39;</span>
<span class="sd">    5</span>
<span class="sd">    &gt;&gt;&gt; for elem in &#39;shazam&#39;:           # update counts from an iterable</span>
<span class="sd">    ...     c[elem] += 1                # by adding 1 to each element&#39;s count</span>
<span class="sd">    &gt;&gt;&gt; c[&#39;a&#39;]                          # now there are seven &#39;a&#39;</span>
<span class="sd">    7</span>
<span class="sd">    &gt;&gt;&gt; del c[&#39;b&#39;]                      # remove all &#39;b&#39;</span>
<span class="sd">    &gt;&gt;&gt; c[&#39;b&#39;]                          # now there are zero &#39;b&#39;</span>
<span class="sd">    0</span>

<span class="sd">    &gt;&gt;&gt; d = Counter(&#39;simsalabim&#39;)       # make another counter</span>
<span class="sd">    &gt;&gt;&gt; c.update(d)                     # add in the second counter</span>
<span class="sd">    &gt;&gt;&gt; c[&#39;a&#39;]                          # now there are nine &#39;a&#39;</span>
<span class="sd">    9</span>

<span class="sd">    &gt;&gt;&gt; c.clear()                       # empty the counter</span>
<span class="sd">    &gt;&gt;&gt; c</span>
<span class="sd">    Counter()</span>

<span class="sd">    Note:  If a count is set to zero or reduced to zero, it will remain</span>
<span class="sd">    in the counter until the entry is deleted or the counter is cleared:</span>

<span class="sd">    &gt;&gt;&gt; c = Counter(&#39;aaabbc&#39;)</span>
<span class="sd">    &gt;&gt;&gt; c[&#39;b&#39;] -= 2                     # reduce the count of &#39;b&#39; by two</span>
<span class="sd">    &gt;&gt;&gt; c.most_common()                 # &#39;b&#39; is still in, but its count is zero</span>
<span class="sd">    [(&#39;a&#39;, 3), (&#39;c&#39;, 1), (&#39;b&#39;, 0)]</span>

<span class="sd">    &#39;&#39;&#39;</span>
    <span class="c1"># References:</span>
    <span class="c1">#   http://en.wikipedia.org/wiki/Multiset</span>
    <span class="c1">#   http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html</span>
    <span class="c1">#   http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm</span>
    <span class="c1">#   http://code.activestate.com/recipes/259174/</span>
    <span class="c1">#   Knuth, TAOCP Vol. II section 4.6.3</span>

    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Create a new, empty Counter object.  And if given, count elements</span>
<span class="sd">        from an input iterable.  Or, initialize the count from another mapping</span>
<span class="sd">        of elements to their counts.</span>

<span class="sd">        &gt;&gt;&gt; c = Counter()                           # a new, empty counter</span>
<span class="sd">        &gt;&gt;&gt; c = Counter(&#39;gallahad&#39;)                 # a new counter from an iterable</span>
<span class="sd">        &gt;&gt;&gt; c = Counter({&#39;a&#39;: 4, &#39;b&#39;: 2})           # a new counter from a mapping</span>
<span class="sd">        &gt;&gt;&gt; c = Counter(a=4, b=2)                   # a new counter from keyword args</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="n">args</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s2">&quot;descriptor &#39;__init__&#39; of &#39;Counter&#39; object &quot;</span>
                            <span class="s2">&quot;needs an argument&quot;</span><span class="p">)</span>
        <span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span> <span class="o">=</span> <span class="n">args</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">)</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s1">&#39;expected at most 1 arguments, got </span><span class="si">%d</span><span class="s1">&#39;</span> <span class="o">%</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">))</span>
        <span class="nb">super</span><span class="p">(</span><span class="n">Counter</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="fm">__init__</span><span class="p">()</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">)</span>

    <span class="k">def</span> <span class="fm">__missing__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="s1">&#39;The count of elements not in the Counter is zero.&#39;</span>
        <span class="c1"># Needed so that self[missing_item] does not raise KeyError</span>
        <span class="k">return</span> <span class="mi">0</span>

    <span class="k">def</span> <span class="nf">most_common</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">n</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;List the n most common elements and their counts from the most</span>
<span class="sd">        common to the least.  If n is None, then list all element counts.</span>

<span class="sd">        &gt;&gt;&gt; Counter(&#39;abcdeabcdabcaba&#39;).most_common(3)</span>
<span class="sd">        [(&#39;a&#39;, 5), (&#39;b&#39;, 4), (&#39;c&#39;, 3)]</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="c1"># Emulate Bag.sortedByCount from Smalltalk</span>
        <span class="k">if</span> <span class="n">n</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
            <span class="k">return</span> <span class="nb">sorted</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">(),</span> <span class="n">key</span><span class="o">=</span><span class="n">_itemgetter</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span> <span class="n">reverse</span><span class="o">=</span><span class="kc">True</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">_heapq</span><span class="o">.</span><span class="n">nlargest</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">(),</span> <span class="n">key</span><span class="o">=</span><span class="n">_itemgetter</span><span class="p">(</span><span class="mi">1</span><span class="p">))</span>

    <span class="k">def</span> <span class="nf">elements</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Iterator over elements repeating each as many times as its count.</span>

<span class="sd">        &gt;&gt;&gt; c = Counter(&#39;ABCABC&#39;)</span>
<span class="sd">        &gt;&gt;&gt; sorted(c.elements())</span>
<span class="sd">        [&#39;A&#39;, &#39;A&#39;, &#39;B&#39;, &#39;B&#39;, &#39;C&#39;, &#39;C&#39;]</span>

<span class="sd">        # Knuth&#39;s example for prime factors of 1836:  2**2 * 3**3 * 17**1</span>
<span class="sd">        &gt;&gt;&gt; prime_factors = Counter({2: 2, 3: 3, 17: 1})</span>
<span class="sd">        &gt;&gt;&gt; product = 1</span>
<span class="sd">        &gt;&gt;&gt; for factor in prime_factors.elements():     # loop over factors</span>
<span class="sd">        ...     product *= factor                       # and multiply them</span>
<span class="sd">        &gt;&gt;&gt; product</span>
<span class="sd">        1836</span>

<span class="sd">        Note, if an element&#39;s count has been set to zero or is a negative</span>
<span class="sd">        number, elements() will ignore it.</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="c1"># Emulate Bag.do from Smalltalk and Multiset.begin from C++.</span>
        <span class="k">return</span> <span class="n">_chain</span><span class="o">.</span><span class="n">from_iterable</span><span class="p">(</span><span class="n">_starmap</span><span class="p">(</span><span class="n">_repeat</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">()))</span>

    <span class="c1"># Override dict methods where necessary</span>

    <span class="nd">@classmethod</span>
    <span class="k">def</span> <span class="nf">fromkeys</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">,</span> <span class="n">v</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="c1"># There is no equivalent method for counters because setting v=1</span>
        <span class="c1"># means that no element can have a count greater than one.</span>
        <span class="k">raise</span> <span class="ne">NotImplementedError</span><span class="p">(</span>
            <span class="s1">&#39;Counter.fromkeys() is undefined.  Use Counter(iterable) instead.&#39;</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">update</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Like dict.update() but add counts instead of replacing them.</span>

<span class="sd">        Source can be an iterable, a dictionary, or another Counter instance.</span>

<span class="sd">        &gt;&gt;&gt; c = Counter(&#39;which&#39;)</span>
<span class="sd">        &gt;&gt;&gt; c.update(&#39;witch&#39;)           # add elements from another iterable</span>
<span class="sd">        &gt;&gt;&gt; d = Counter(&#39;watch&#39;)</span>
<span class="sd">        &gt;&gt;&gt; c.update(d)                 # add elements from another counter</span>
<span class="sd">        &gt;&gt;&gt; c[&#39;h&#39;]                      # four &#39;h&#39; in which, witch, and watch</span>
<span class="sd">        4</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="c1"># The regular dict.update() operation makes no sense here because the</span>
        <span class="c1"># replace behavior results in the some of original untouched counts</span>
        <span class="c1"># being mixed-in with all of the other counts for a mismash that</span>
        <span class="c1"># doesn&#39;t have a straight-forward interpretation in most counting</span>
        <span class="c1"># contexts.  Instead, we implement straight-addition.  Both the inputs</span>
        <span class="c1"># and outputs are allowed to contain zero and negative counts.</span>

        <span class="k">if</span> <span class="ow">not</span> <span class="n">args</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s2">&quot;descriptor &#39;update&#39; of &#39;Counter&#39; object &quot;</span>
                            <span class="s2">&quot;needs an argument&quot;</span><span class="p">)</span>
        <span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span> <span class="o">=</span> <span class="n">args</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">)</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s1">&#39;expected at most 1 arguments, got </span><span class="si">%d</span><span class="s1">&#39;</span> <span class="o">%</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">))</span>
        <span class="n">iterable</span> <span class="o">=</span> <span class="n">args</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="k">if</span> <span class="n">args</span> <span class="k">else</span> <span class="kc">None</span>
        <span class="k">if</span> <span class="n">iterable</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
            <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">iterable</span><span class="p">,</span> <span class="n">_collections_abc</span><span class="o">.</span><span class="n">Mapping</span><span class="p">):</span>
                <span class="k">if</span> <span class="bp">self</span><span class="p">:</span>
                    <span class="n">self_get</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">get</span>
                    <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">iterable</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
                        <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">count</span> <span class="o">+</span> <span class="n">self_get</span><span class="p">(</span><span class="n">elem</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
                <span class="k">else</span><span class="p">:</span>
                    <span class="nb">super</span><span class="p">(</span><span class="n">Counter</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">iterable</span><span class="p">)</span> <span class="c1"># fast path when counter is empty</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="n">_count_elements</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">iterable</span><span class="p">)</span>
        <span class="k">if</span> <span class="n">kwds</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">kwds</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">subtract</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Like dict.update() but subtracts counts instead of replacing them.</span>
<span class="sd">        Counts can be reduced below zero.  Both the inputs and outputs are</span>
<span class="sd">        allowed to contain zero and negative counts.</span>

<span class="sd">        Source can be an iterable, a dictionary, or another Counter instance.</span>

<span class="sd">        &gt;&gt;&gt; c = Counter(&#39;which&#39;)</span>
<span class="sd">        &gt;&gt;&gt; c.subtract(&#39;witch&#39;)             # subtract elements from another iterable</span>
<span class="sd">        &gt;&gt;&gt; c.subtract(Counter(&#39;watch&#39;))    # subtract elements from another counter</span>
<span class="sd">        &gt;&gt;&gt; c[&#39;h&#39;]                          # 2 in which, minus 1 in witch, minus 1 in watch</span>
<span class="sd">        0</span>
<span class="sd">        &gt;&gt;&gt; c[&#39;w&#39;]                          # 1 in which, minus 1 in witch, minus 1 in watch</span>
<span class="sd">        -1</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="n">args</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s2">&quot;descriptor &#39;subtract&#39; of &#39;Counter&#39; object &quot;</span>
                            <span class="s2">&quot;needs an argument&quot;</span><span class="p">)</span>
        <span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span> <span class="o">=</span> <span class="n">args</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">)</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s1">&#39;expected at most 1 arguments, got </span><span class="si">%d</span><span class="s1">&#39;</span> <span class="o">%</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">))</span>
        <span class="n">iterable</span> <span class="o">=</span> <span class="n">args</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="k">if</span> <span class="n">args</span> <span class="k">else</span> <span class="kc">None</span>
        <span class="k">if</span> <span class="n">iterable</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
            <span class="n">self_get</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">get</span>
            <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">iterable</span><span class="p">,</span> <span class="n">_collections_abc</span><span class="o">.</span><span class="n">Mapping</span><span class="p">):</span>
                <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">iterable</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
                    <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">self_get</span><span class="p">(</span><span class="n">elem</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="o">-</span> <span class="n">count</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="k">for</span> <span class="n">elem</span> <span class="ow">in</span> <span class="n">iterable</span><span class="p">:</span>
                    <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">self_get</span><span class="p">(</span><span class="n">elem</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span>
        <span class="k">if</span> <span class="n">kwds</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">subtract</span><span class="p">(</span><span class="n">kwds</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;Return a shallow copy.&#39;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">__reduce__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">,</span> <span class="p">(</span><span class="nb">dict</span><span class="p">(</span><span class="bp">self</span><span class="p">),)</span>

    <span class="k">def</span> <span class="fm">__delitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">elem</span><span class="p">):</span>
        <span class="s1">&#39;Like dict.__delitem__() but does not raise KeyError for missing values.&#39;</span>
        <span class="k">if</span> <span class="n">elem</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="nb">super</span><span class="p">()</span><span class="o">.</span><span class="fm">__delitem__</span><span class="p">(</span><span class="n">elem</span><span class="p">)</span>

    <span class="k">def</span> <span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="p">:</span>
            <span class="k">return</span> <span class="s1">&#39;</span><span class="si">%s</span><span class="s1">()&#39;</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="n">items</span> <span class="o">=</span> <span class="s1">&#39;, &#39;</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="s1">&#39;</span><span class="si">%r</span><span class="s1">: </span><span class="si">%r</span><span class="s1">&#39;</span><span class="o">.</span><span class="fm">__mod__</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">most_common</span><span class="p">()))</span>
            <span class="k">return</span> <span class="s1">&#39;</span><span class="si">%s</span><span class="s1">({</span><span class="si">%s</span><span class="s1">})&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span><span class="p">,</span> <span class="n">items</span><span class="p">)</span>
        <span class="k">except</span> <span class="ne">TypeError</span><span class="p">:</span>
            <span class="c1"># handle case where values are not orderable</span>
            <span class="k">return</span> <span class="s1">&#39;</span><span class="si">{0}</span><span class="s1">(</span><span class="si">{1!r}</span><span class="s1">)&#39;</span><span class="o">.</span><span class="n">format</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span><span class="p">,</span> <span class="nb">dict</span><span class="p">(</span><span class="bp">self</span><span class="p">))</span>

    <span class="c1"># Multiset-style mathematical operations discussed in:</span>
    <span class="c1">#       Knuth TAOCP Volume II section 4.6.3 exercise 19</span>
    <span class="c1">#       and at http://en.wikipedia.org/wiki/Multiset</span>
    <span class="c1">#</span>
    <span class="c1"># Outputs guaranteed to only include positive counts.</span>
    <span class="c1">#</span>
    <span class="c1"># To strip negative and zero counts, add-in an empty counter:</span>
    <span class="c1">#       c += Counter()</span>

    <span class="k">def</span> <span class="fm">__add__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Add counts from two counters.</span>

<span class="sd">        &gt;&gt;&gt; Counter(&#39;abbb&#39;) + Counter(&#39;bcc&#39;)</span>
<span class="sd">        Counter({&#39;b&#39;: 4, &#39;c&#39;: 2, &#39;a&#39;: 1})</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">NotImplemented</span>
        <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="n">newcount</span> <span class="o">=</span> <span class="n">count</span> <span class="o">+</span> <span class="n">other</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
            <span class="k">if</span> <span class="n">newcount</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">newcount</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="k">if</span> <span class="n">elem</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span> <span class="ow">and</span> <span class="n">count</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">count</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="k">def</span> <span class="fm">__sub__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39; Subtract count, but keep only results with positive counts.</span>

<span class="sd">        &gt;&gt;&gt; Counter(&#39;abbbc&#39;) - Counter(&#39;bccd&#39;)</span>
<span class="sd">        Counter({&#39;b&#39;: 2, &#39;a&#39;: 1})</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">NotImplemented</span>
        <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="n">newcount</span> <span class="o">=</span> <span class="n">count</span> <span class="o">-</span> <span class="n">other</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
            <span class="k">if</span> <span class="n">newcount</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">newcount</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="k">if</span> <span class="n">elem</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span> <span class="ow">and</span> <span class="n">count</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">:</span>
                <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span> <span class="o">-</span> <span class="n">count</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="k">def</span> <span class="fm">__or__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Union is the maximum of value in either of the input counters.</span>

<span class="sd">        &gt;&gt;&gt; Counter(&#39;abbb&#39;) | Counter(&#39;bcc&#39;)</span>
<span class="sd">        Counter({&#39;b&#39;: 3, &#39;c&#39;: 2, &#39;a&#39;: 1})</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">NotImplemented</span>
        <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="n">other_count</span> <span class="o">=</span> <span class="n">other</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
            <span class="n">newcount</span> <span class="o">=</span> <span class="n">other_count</span> <span class="k">if</span> <span class="n">count</span> <span class="o">&lt;</span> <span class="n">other_count</span> <span class="k">else</span> <span class="n">count</span>
            <span class="k">if</span> <span class="n">newcount</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">newcount</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="k">if</span> <span class="n">elem</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span> <span class="ow">and</span> <span class="n">count</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">count</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="k">def</span> <span class="fm">__and__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39; Intersection is the minimum of corresponding counts.</span>

<span class="sd">        &gt;&gt;&gt; Counter(&#39;abbb&#39;) &amp; Counter(&#39;bcc&#39;)</span>
<span class="sd">        Counter({&#39;b&#39;: 1})</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">NotImplemented</span>
        <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="n">other_count</span> <span class="o">=</span> <span class="n">other</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
            <span class="n">newcount</span> <span class="o">=</span> <span class="n">count</span> <span class="k">if</span> <span class="n">count</span> <span class="o">&lt;</span> <span class="n">other_count</span> <span class="k">else</span> <span class="n">other_count</span>
            <span class="k">if</span> <span class="n">newcount</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">newcount</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="k">def</span> <span class="fm">__pos__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;Adds an empty counter, effectively stripping negative and zero counts&#39;</span>
        <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="k">if</span> <span class="n">count</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">count</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="k">def</span> <span class="fm">__neg__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Subtracts from an empty counter.  Strips positive and zero counts,</span>
<span class="sd">        and flips the sign on negative counts.</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="k">if</span> <span class="n">count</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">:</span>
                <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span> <span class="o">-</span> <span class="n">count</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="k">def</span> <span class="nf">_keep_positive</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Internal method to strip elements with a negative or zero count&#39;&#39;&#39;</span>
        <span class="n">nonpositive</span> <span class="o">=</span> <span class="p">[</span><span class="n">elem</span> <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">()</span> <span class="k">if</span> <span class="ow">not</span> <span class="n">count</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">]</span>
        <span class="k">for</span> <span class="n">elem</span> <span class="ow">in</span> <span class="n">nonpositive</span><span class="p">:</span>
            <span class="k">del</span> <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
        <span class="k">return</span> <span class="bp">self</span>

    <span class="k">def</span> <span class="fm">__iadd__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Inplace add from another counter, keeping only positive counts.</span>

<span class="sd">        &gt;&gt;&gt; c = Counter(&#39;abbb&#39;)</span>
<span class="sd">        &gt;&gt;&gt; c += Counter(&#39;bcc&#39;)</span>
<span class="sd">        &gt;&gt;&gt; c</span>
<span class="sd">        Counter({&#39;b&#39;: 4, &#39;c&#39;: 2, &#39;a&#39;: 1})</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">+=</span> <span class="n">count</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_keep_positive</span><span class="p">()</span>

    <span class="k">def</span> <span class="fm">__isub__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Inplace subtract counter, but keep only results with positive counts.</span>

<span class="sd">        &gt;&gt;&gt; c = Counter(&#39;abbbc&#39;)</span>
<span class="sd">        &gt;&gt;&gt; c -= Counter(&#39;bccd&#39;)</span>
<span class="sd">        &gt;&gt;&gt; c</span>
<span class="sd">        Counter({&#39;b&#39;: 2, &#39;a&#39;: 1})</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">-=</span> <span class="n">count</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_keep_positive</span><span class="p">()</span>

    <span class="k">def</span> <span class="fm">__ior__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Inplace union is the maximum of value from either counter.</span>

<span class="sd">        &gt;&gt;&gt; c = Counter(&#39;abbb&#39;)</span>
<span class="sd">        &gt;&gt;&gt; c |= Counter(&#39;bcc&#39;)</span>
<span class="sd">        &gt;&gt;&gt; c</span>
<span class="sd">        Counter({&#39;b&#39;: 3, &#39;c&#39;: 2, &#39;a&#39;: 1})</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">other_count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="n">count</span> <span class="o">=</span> <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
            <span class="k">if</span> <span class="n">other_count</span> <span class="o">&gt;</span> <span class="n">count</span><span class="p">:</span>
                <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">other_count</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_keep_positive</span><span class="p">()</span>

    <span class="k">def</span> <span class="fm">__iand__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Inplace intersection is the minimum of corresponding counts.</span>

<span class="sd">        &gt;&gt;&gt; c = Counter(&#39;abbb&#39;)</span>
<span class="sd">        &gt;&gt;&gt; c &amp;= Counter(&#39;bcc&#39;)</span>
<span class="sd">        &gt;&gt;&gt; c</span>
<span class="sd">        Counter({&#39;b&#39;: 1})</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
            <span class="n">other_count</span> <span class="o">=</span> <span class="n">other</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
            <span class="k">if</span> <span class="n">other_count</span> <span class="o">&lt;</span> <span class="n">count</span><span class="p">:</span>
                <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">other_count</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_keep_positive</span><span class="p">()</span>


<span class="c1">########################################################################</span>
<span class="c1">###  ChainMap</span>
<span class="c1">########################################################################</span>

<span class="k">class</span> <span class="nc">ChainMap</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableMapping</span><span class="p">):</span>
    <span class="sd">&#39;&#39;&#39; A ChainMap groups multiple dicts (or other mappings) together</span>
<span class="sd">    to create a single, updateable view.</span>

<span class="sd">    The underlying mappings are stored in a list.  That list is public and can</span>
<span class="sd">    be accessed or updated using the *maps* attribute.  There is no other</span>
<span class="sd">    state.</span>

<span class="sd">    Lookups search the underlying mappings successively until a key is found.</span>
<span class="sd">    In contrast, writes, updates, and deletions only operate on the first</span>
<span class="sd">    mapping.</span>

<span class="sd">    &#39;&#39;&#39;</span>

    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">maps</span><span class="p">):</span>
        <span class="sd">&#39;&#39;&#39;Initialize a ChainMap by setting *maps* to the given mappings.</span>
<span class="sd">        If no mappings are provided, a single empty dictionary is used.</span>

<span class="sd">        &#39;&#39;&#39;</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">maps</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">maps</span><span class="p">)</span> <span class="ow">or</span> <span class="p">[{}]</span>          <span class="c1"># always at least one map</span>

    <span class="k">def</span> <span class="fm">__missing__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>

    <span class="k">def</span> <span class="fm">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">mapping</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">:</span>
            <span class="k">try</span><span class="p">:</span>
                <span class="k">return</span> <span class="n">mapping</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>             <span class="c1"># can&#39;t use &#39;key in mapping&#39; with defaultdict</span>
            <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
                <span class="k">pass</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="fm">__missing__</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>            <span class="c1"># support subclasses that define __missing__</span>

    <span class="k">def</span> <span class="nf">get</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="k">if</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span> <span class="k">else</span> <span class="n">default</span>

    <span class="k">def</span> <span class="fm">__len__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">len</span><span class="p">(</span><span class="nb">set</span><span class="p">()</span><span class="o">.</span><span class="n">union</span><span class="p">(</span><span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">))</span>     <span class="c1"># reuses stored hash values if possible</span>

    <span class="k">def</span> <span class="fm">__iter__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="n">d</span> <span class="o">=</span> <span class="p">{}</span>
        <span class="k">for</span> <span class="n">mapping</span> <span class="ow">in</span> <span class="nb">reversed</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">):</span>
            <span class="n">d</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">mapping</span><span class="p">)</span>                   <span class="c1"># reuses stored hash values if possible</span>
        <span class="k">return</span> <span class="nb">iter</span><span class="p">(</span><span class="n">d</span><span class="p">)</span>

    <span class="k">def</span> <span class="fm">__contains__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">any</span><span class="p">(</span><span class="n">key</span> <span class="ow">in</span> <span class="n">m</span> <span class="k">for</span> <span class="n">m</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">)</span>

    <span class="k">def</span> <span class="fm">__bool__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">any</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">)</span>

    <span class="nd">@_recursive_repr</span><span class="p">()</span>
    <span class="k">def</span> <span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="s1">&#39;</span><span class="si">{0.__class__.__name__}</span><span class="s1">(</span><span class="si">{1}</span><span class="s1">)&#39;</span><span class="o">.</span><span class="n">format</span><span class="p">(</span>
            <span class="bp">self</span><span class="p">,</span> <span class="s1">&#39;, &#39;</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="nb">repr</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">)))</span>

    <span class="nd">@classmethod</span>
    <span class="k">def</span> <span class="nf">fromkeys</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
        <span class="s1">&#39;Create a ChainMap with a single dict created from the iterable.&#39;</span>
        <span class="k">return</span> <span class="bp">cls</span><span class="p">(</span><span class="nb">dict</span><span class="o">.</span><span class="n">fromkeys</span><span class="p">(</span><span class="n">iterable</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">))</span>

    <span class="k">def</span> <span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]&#39;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">copy</span><span class="p">(),</span> <span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">1</span><span class="p">:])</span>

    <span class="n">__copy__</span> <span class="o">=</span> <span class="n">copy</span>

    <span class="k">def</span> <span class="nf">new_child</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">m</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>                <span class="c1"># like Django&#39;s Context.push()</span>
        <span class="sd">&#39;&#39;&#39;New ChainMap with a new map followed by all previous maps.</span>
<span class="sd">        If no map is provided, an empty dict is used.</span>
<span class="sd">        &#39;&#39;&#39;</span>
        <span class="k">if</span> <span class="n">m</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
            <span class="n">m</span> <span class="o">=</span> <span class="p">{}</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">m</span><span class="p">,</span> <span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">)</span>

    <span class="nd">@property</span>
    <span class="k">def</span> <span class="nf">parents</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>                          <span class="c1"># like Django&#39;s Context.pop()</span>
        <span class="s1">&#39;New ChainMap from maps[1:].&#39;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">1</span><span class="p">:])</span>

    <span class="k">def</span> <span class="fm">__setitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">value</span>

    <span class="k">def</span> <span class="fm">__delitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="n">key</span><span class="p">]</span>
        <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="s1">&#39;Key not found in the first mapping: </span><span class="si">{!r}</span><span class="s1">&#39;</span><span class="o">.</span><span class="n">format</span><span class="p">(</span><span class="n">key</span><span class="p">))</span>

    <span class="k">def</span> <span class="nf">popitem</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.&#39;</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">popitem</span><span class="p">()</span>
        <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="s1">&#39;No keys found in the first mapping.&#39;</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">pop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
        <span class="s1">&#39;Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].&#39;</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">)</span>
        <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="s1">&#39;Key not found in the first mapping: </span><span class="si">{!r}</span><span class="s1">&#39;</span><span class="o">.</span><span class="n">format</span><span class="p">(</span><span class="n">key</span><span class="p">))</span>

    <span class="k">def</span> <span class="nf">clear</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="s1">&#39;Clear maps[0], leaving maps[1:] intact.&#39;</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">clear</span><span class="p">()</span>


<span class="c1">################################################################################</span>
<span class="c1">### UserDict</span>
<span class="c1">################################################################################</span>

<span class="k">class</span> <span class="nc">UserDict</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableMapping</span><span class="p">):</span>

    <span class="c1"># Start by filling-out the abstract methods</span>
    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="n">args</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s2">&quot;descriptor &#39;__init__&#39; of &#39;UserDict&#39; object &quot;</span>
                            <span class="s2">&quot;needs an argument&quot;</span><span class="p">)</span>
        <span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span> <span class="o">=</span> <span class="n">args</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">)</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s1">&#39;expected at most 1 arguments, got </span><span class="si">%d</span><span class="s1">&#39;</span> <span class="o">%</span> <span class="nb">len</span><span class="p">(</span><span class="n">args</span><span class="p">))</span>
        <span class="k">if</span> <span class="n">args</span><span class="p">:</span>
            <span class="nb">dict</span> <span class="o">=</span> <span class="n">args</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
        <span class="k">elif</span> <span class="s1">&#39;dict&#39;</span> <span class="ow">in</span> <span class="n">kwargs</span><span class="p">:</span>
            <span class="nb">dict</span> <span class="o">=</span> <span class="n">kwargs</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="s1">&#39;dict&#39;</span><span class="p">)</span>
            <span class="kn">import</span> <span class="nn">warnings</span>
            <span class="n">warnings</span><span class="o">.</span><span class="n">warn</span><span class="p">(</span><span class="s2">&quot;Passing &#39;dict&#39; as keyword argument is deprecated&quot;</span><span class="p">,</span>
                          <span class="ne">DeprecationWarning</span><span class="p">,</span> <span class="n">stacklevel</span><span class="o">=</span><span class="mi">2</span><span class="p">)</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="nb">dict</span> <span class="o">=</span> <span class="kc">None</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="p">{}</span>
        <span class="k">if</span> <span class="nb">dict</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="nb">dict</span><span class="p">)</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">kwargs</span><span class="p">):</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">kwargs</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__len__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
        <span class="k">if</span> <span class="nb">hasattr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">,</span> <span class="s2">&quot;__missing__&quot;</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="fm">__missing__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">)</span>
        <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__setitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">item</span>
    <span class="k">def</span> <span class="fm">__delitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span> <span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
    <span class="k">def</span> <span class="fm">__iter__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">iter</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

    <span class="c1"># Modify __contains__ to work correctly when __missing__ is present</span>
    <span class="k">def</span> <span class="fm">__contains__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
        <span class="k">return</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span>

    <span class="c1"># Now, add the methods in dicts but not in MutableMapping</span>
    <span class="k">def</span> <span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">__copy__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="n">inst</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="fm">__new__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">)</span>
        <span class="n">inst</span><span class="o">.</span><span class="vm">__dict__</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">)</span>
        <span class="c1"># Create a copy and avoid triggering descriptors</span>
        <span class="n">inst</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">[</span><span class="s2">&quot;data&quot;</span><span class="p">]</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">[</span><span class="s2">&quot;data&quot;</span><span class="p">]</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span>
        <span class="k">return</span> <span class="n">inst</span>

    <span class="k">def</span> <span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span> <span class="ow">is</span> <span class="n">UserDict</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">UserDict</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">copy</span><span class="p">())</span>
        <span class="kn">import</span> <span class="nn">copy</span>
        <span class="n">data</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="p">{}</span>
            <span class="n">c</span> <span class="o">=</span> <span class="n">copy</span><span class="o">.</span><span class="n">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>
        <span class="k">finally</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="n">data</span>
        <span class="n">c</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">c</span>

    <span class="nd">@classmethod</span>
    <span class="k">def</span> <span class="nf">fromkeys</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">,</span> <span class="n">value</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="n">d</span> <span class="o">=</span> <span class="bp">cls</span><span class="p">()</span>
        <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="n">iterable</span><span class="p">:</span>
            <span class="n">d</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">value</span>
        <span class="k">return</span> <span class="n">d</span>



<span class="c1">################################################################################</span>
<span class="c1">### UserList</span>
<span class="c1">################################################################################</span>

<span class="k">class</span> <span class="nc">UserList</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableSequence</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;A more or less complete user-defined wrapper around list objects.&quot;&quot;&quot;</span>
    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">initlist</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="k">if</span> <span class="n">initlist</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
            <span class="c1"># XXX should this accept an arbitrary sequence?</span>
            <span class="k">if</span> <span class="nb">type</span><span class="p">(</span><span class="n">initlist</span><span class="p">)</span> <span class="o">==</span> <span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">):</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[:]</span> <span class="o">=</span> <span class="n">initlist</span>
            <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">initlist</span><span class="p">,</span> <span class="n">UserList</span><span class="p">):</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[:]</span> <span class="o">=</span> <span class="n">initlist</span><span class="o">.</span><span class="n">data</span><span class="p">[:]</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">initlist</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__lt__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;</span>  <span class="bp">self</span><span class="o">.</span><span class="n">__cast</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__le__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__cast</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">__cast</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__gt__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;</span>  <span class="bp">self</span><span class="o">.</span><span class="n">__cast</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__ge__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__cast</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">__cast</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="k">return</span> <span class="n">other</span><span class="o">.</span><span class="n">data</span> <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserList</span><span class="p">)</span> <span class="k">else</span> <span class="n">other</span>
    <span class="k">def</span> <span class="fm">__contains__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span> <span class="k">return</span> <span class="n">item</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span>
    <span class="k">def</span> <span class="fm">__len__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="nb">slice</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
    <span class="k">def</span> <span class="fm">__setitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">item</span>
    <span class="k">def</span> <span class="fm">__delitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="p">):</span> <span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
    <span class="k">def</span> <span class="fm">__add__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserList</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="n">other</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
        <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="n">other</span><span class="p">)</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="nb">list</span><span class="p">(</span><span class="n">other</span><span class="p">))</span>
    <span class="k">def</span> <span class="fm">__radd__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserList</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">other</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
        <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">other</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="nb">list</span><span class="p">(</span><span class="n">other</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__iadd__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserList</span><span class="p">):</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+=</span> <span class="n">other</span><span class="o">.</span><span class="n">data</span>
        <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)):</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+=</span> <span class="n">other</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+=</span> <span class="nb">list</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
        <span class="k">return</span> <span class="bp">self</span>
    <span class="k">def</span> <span class="fm">__mul__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">*</span><span class="n">n</span><span class="p">)</span>
    <span class="fm">__rmul__</span> <span class="o">=</span> <span class="fm">__mul__</span>
    <span class="k">def</span> <span class="fm">__imul__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">*=</span> <span class="n">n</span>
        <span class="k">return</span> <span class="bp">self</span>
    <span class="k">def</span> <span class="nf">__copy__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="n">inst</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="fm">__new__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">)</span>
        <span class="n">inst</span><span class="o">.</span><span class="vm">__dict__</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">)</span>
        <span class="c1"># Create a copy and avoid triggering descriptors</span>
        <span class="n">inst</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">[</span><span class="s2">&quot;data&quot;</span><span class="p">]</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">[</span><span class="s2">&quot;data&quot;</span><span class="p">][:]</span>
        <span class="k">return</span> <span class="n">inst</span>
    <span class="k">def</span> <span class="nf">append</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">item</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">insert</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">insert</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">item</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">pop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="o">=-</span><span class="mi">1</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">remove</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">item</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">clear</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">clear</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">count</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">count</span><span class="p">(</span><span class="n">item</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">index</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">index</span><span class="p">(</span><span class="n">item</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">reverse</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">reverse</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">sort</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">sort</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">extend</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserList</span><span class="p">):</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">other</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>



<span class="c1">################################################################################</span>
<span class="c1">### UserString</span>
<span class="c1">################################################################################</span>

<span class="k">class</span> <span class="nc">UserString</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">Sequence</span><span class="p">):</span>
    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">seq</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">seq</span><span class="p">,</span> <span class="nb">str</span><span class="p">):</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="n">seq</span>
        <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">seq</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="n">seq</span><span class="o">.</span><span class="n">data</span><span class="p">[:]</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="nb">str</span><span class="p">(</span><span class="n">seq</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__str__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">str</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__int__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">int</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__float__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">float</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__complex__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">complex</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__hash__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">hash</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">__getnewargs__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[:],)</span>

    <span class="k">def</span> <span class="fm">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">string</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">string</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">==</span> <span class="n">string</span><span class="o">.</span><span class="n">data</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">==</span> <span class="n">string</span>
    <span class="k">def</span> <span class="fm">__lt__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">string</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">string</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;</span> <span class="n">string</span><span class="o">.</span><span class="n">data</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;</span> <span class="n">string</span>
    <span class="k">def</span> <span class="fm">__le__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">string</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">string</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;=</span> <span class="n">string</span><span class="o">.</span><span class="n">data</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;=</span> <span class="n">string</span>
    <span class="k">def</span> <span class="fm">__gt__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">string</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">string</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;</span> <span class="n">string</span><span class="o">.</span><span class="n">data</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;</span> <span class="n">string</span>
    <span class="k">def</span> <span class="fm">__ge__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">string</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">string</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;=</span> <span class="n">string</span><span class="o">.</span><span class="n">data</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;=</span> <span class="n">string</span>

    <span class="k">def</span> <span class="fm">__contains__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">char</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">char</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="n">char</span> <span class="o">=</span> <span class="n">char</span><span class="o">.</span><span class="n">data</span>
        <span class="k">return</span> <span class="n">char</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span>

    <span class="k">def</span> <span class="fm">__len__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">index</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">index</span><span class="p">])</span>
    <span class="k">def</span> <span class="fm">__add__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="n">other</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
        <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">str</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="n">other</span><span class="p">)</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="nb">str</span><span class="p">(</span><span class="n">other</span><span class="p">))</span>
    <span class="k">def</span> <span class="fm">__radd__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">str</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">other</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="nb">str</span><span class="p">(</span><span class="n">other</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__mul__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">*</span><span class="n">n</span><span class="p">)</span>
    <span class="fm">__rmul__</span> <span class="o">=</span> <span class="fm">__mul__</span>
    <span class="k">def</span> <span class="fm">__mod__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">args</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">%</span> <span class="n">args</span><span class="p">)</span>
    <span class="k">def</span> <span class="fm">__rmod__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="nb">format</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="nb">format</span> <span class="o">%</span> <span class="n">args</span><span class="p">)</span>

    <span class="c1"># the following methods are defined in alphabetical order:</span>
    <span class="k">def</span> <span class="nf">capitalize</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">capitalize</span><span class="p">())</span>
    <span class="k">def</span> <span class="nf">casefold</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">casefold</span><span class="p">())</span>
    <span class="k">def</span> <span class="nf">center</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">center</span><span class="p">(</span><span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">))</span>
    <span class="k">def</span> <span class="nf">count</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="n">sub</span> <span class="o">=</span> <span class="n">sub</span><span class="o">.</span><span class="n">data</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">count</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">encode</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">encoding</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">errors</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span> <span class="c1"># XXX improve this?</span>
        <span class="k">if</span> <span class="n">encoding</span><span class="p">:</span>
            <span class="k">if</span> <span class="n">errors</span><span class="p">:</span>
                <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">encode</span><span class="p">(</span><span class="n">encoding</span><span class="p">,</span> <span class="n">errors</span><span class="p">))</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">encode</span><span class="p">(</span><span class="n">encoding</span><span class="p">))</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">encode</span><span class="p">())</span>
    <span class="k">def</span> <span class="nf">endswith</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">suffix</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">endswith</span><span class="p">(</span><span class="n">suffix</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">expandtabs</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">tabsize</span><span class="o">=</span><span class="mi">8</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">expandtabs</span><span class="p">(</span><span class="n">tabsize</span><span class="p">))</span>
    <span class="k">def</span> <span class="nf">find</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="n">sub</span> <span class="o">=</span> <span class="n">sub</span><span class="o">.</span><span class="n">data</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">find</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">format</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">format</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">format_map</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">mapping</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">format_map</span><span class="p">(</span><span class="n">mapping</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">index</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">index</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">isalpha</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isalpha</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">isalnum</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isalnum</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">isascii</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isascii</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">isdecimal</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isdecimal</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">isdigit</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isdigit</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">isidentifier</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isidentifier</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">islower</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">islower</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">isnumeric</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isnumeric</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">isprintable</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isprintable</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">isspace</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isspace</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">istitle</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">istitle</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">isupper</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isupper</span><span class="p">()</span>
    <span class="k">def</span> <span class="nf">join</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">seq</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="n">seq</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">ljust</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">ljust</span><span class="p">(</span><span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">))</span>
    <span class="k">def</span> <span class="nf">lower</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">lower</span><span class="p">())</span>
    <span class="k">def</span> <span class="nf">lstrip</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">chars</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">lstrip</span><span class="p">(</span><span class="n">chars</span><span class="p">))</span>
    <span class="n">maketrans</span> <span class="o">=</span> <span class="nb">str</span><span class="o">.</span><span class="n">maketrans</span>
    <span class="k">def</span> <span class="nf">partition</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sep</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">partition</span><span class="p">(</span><span class="n">sep</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">replace</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">old</span><span class="p">,</span> <span class="n">new</span><span class="p">,</span> <span class="n">maxsplit</span><span class="o">=-</span><span class="mi">1</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">old</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="n">old</span> <span class="o">=</span> <span class="n">old</span><span class="o">.</span><span class="n">data</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">new</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="n">new</span> <span class="o">=</span> <span class="n">new</span><span class="o">.</span><span class="n">data</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">replace</span><span class="p">(</span><span class="n">old</span><span class="p">,</span> <span class="n">new</span><span class="p">,</span> <span class="n">maxsplit</span><span class="p">))</span>
    <span class="k">def</span> <span class="nf">rfind</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
            <span class="n">sub</span> <span class="o">=</span> <span class="n">sub</span><span class="o">.</span><span class="n">data</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rfind</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">rindex</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rindex</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">rjust</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rjust</span><span class="p">(</span><span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">))</span>
    <span class="k">def</span> <span class="nf">rpartition</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sep</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rpartition</span><span class="p">(</span><span class="n">sep</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">rstrip</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">chars</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rstrip</span><span class="p">(</span><span class="n">chars</span><span class="p">))</span>
    <span class="k">def</span> <span class="nf">split</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sep</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">maxsplit</span><span class="o">=-</span><span class="mi">1</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">split</span><span class="p">(</span><span class="n">sep</span><span class="p">,</span> <span class="n">maxsplit</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">rsplit</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sep</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">maxsplit</span><span class="o">=-</span><span class="mi">1</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rsplit</span><span class="p">(</span><span class="n">sep</span><span class="p">,</span> <span class="n">maxsplit</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">splitlines</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">keepends</span><span class="o">=</span><span class="kc">False</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">splitlines</span><span class="p">(</span><span class="n">keepends</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">startswith</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">prefix</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">startswith</span><span class="p">(</span><span class="n">prefix</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>
    <span class="k">def</span> <span class="nf">strip</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">chars</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">strip</span><span class="p">(</span><span class="n">chars</span><span class="p">))</span>
    <span class="k">def</span> <span class="nf">swapcase</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">swapcase</span><span class="p">())</span>
    <span class="k">def</span> <span class="nf">title</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">title</span><span class="p">())</span>
    <span class="k">def</span> <span class="nf">translate</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">translate</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">))</span>
    <span class="k">def</span> <span class="nf">upper</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">upper</span><span class="p">())</span>
    <span class="k">def</span> <span class="nf">zfill</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">width</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">zfill</span><span class="p">(</span><span class="n">width</span><span class="p">))</span>
</pre></div>

          </div>
          
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
<p class="logo">
  <a href="../index.html">
    <img class="logo" src="../_static/../../../../figs/icon.png" alt="Logo"/>
    
  </a>
</p>



<p class="blurb">Spatial maths and geometry for Python</p>




<p>
<iframe src="https://ghbtns.com/github-btn.html?user=petercorke&repo=spatialmath-python&type=watch&count=true&size=large&v=2"
  allowtransparency="true" frameborder="0" scrolling="0" width="200px" height="35px"></iframe>
</p>





<h3>Navigation</h3>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../intro.html">Introduction</a></li>
<li class="toctree-l1"><a class="reference internal" href="../spatialmath.html">Classes and functions</a></li>
<li class="toctree-l1"><a class="reference internal" href="../indices.html">Indices</a></li>
</ul>

<div class="relations">
<h3>Related Topics</h3>
<ul>
  <li><a href="../index.html">Documentation overview</a><ul>
  <li><a href="index.html">Module code</a><ul>
  </ul></li>
  </ul></li>
</ul>
</div>
<div id="searchbox" style="display: none" role="search">
  <h3 id="searchlabel">Quick search</h3>
    <div class="searchformwrapper">
    <form class="search" action="../search.html" method="get">
      <input type="text" name="q" aria-labelledby="searchlabel" />
      <input type="submit" value="Go" />
    </form>
    </div>
</div>
<script>$('#searchbox').show(0);</script>








        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="footer">
      &copy;2020, Peter Corke.
      
      |
      Powered by <a href="http://sphinx-doc.org/">Sphinx 2.4.4</a>
      &amp; <a href="https://github.com/bitprophet/alabaster">Alabaster 0.7.12</a>
      
    </div>

    

    
  </body>
</html>